/* *
* 通过统计待排序元素中每个元素出现的次数来确定每个元素的相对位置 时间复杂度为O(n+k)，其中n为待排序元素个数，k为元素的取值范围，空间复杂度为O(k) 稳定
* 待排序数组每一个元素要求是非负整数
* 流程如下：
* 1.找出最大最小值
* 2.创建长度为最大值减去最小值+1的数组
* 3.数组统计每个值的出现次数(根据与最小值的差值来决定索引)
* 4.根据前面的数组，计算每个值的位置
* 5.遍历 将数值对应到新数组中
* */

function countingSort(arr) {

    let min = Infinity
    let max = -Infinity
    const resArr = []
    for (let i = 0; i < arr.length; i ++) {
        if (arr[i] > max) max = arr[i]
        if (arr[i] < min) min = arr[i]
    }
    const indexArr = new Array(max - min + 1).fill(0)
    for (let i = 0; i < arr.length; i ++) {
        indexArr[arr[i] - min] += 1
    }

    for (let i = 0; i < indexArr.length; i ++) {
        while (indexArr[i] !== 0) {
            resArr.push(i + min)
            indexArr[i] --
        }
    }

    return resArr
}

const arr = [5,2,6,1,7,2,10,8]
console.log(countingSort(arr));
